๐Ÿ‘ฉโ€๐Ÿ’ป 81304. ๋ฏธ๋กœ ํƒˆ์ถœ

@Seongukbaek Posted May 06, 2022 ยท Updated May 06, 2022 ยท 7 min read

๋ฌธ์ œ

Programmers - ๋ฏธ๋กœ ํƒˆ์ถœ

๐Ÿ“ Logic

class Node implements Comparable<Node> { int to; int weight; int status; public Node(int to, int weight, int status) { this.to = to; this.weight = weight; this.status = status; } // ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ์œ„ํ•จ, ์—ฌ๋Ÿฌ ๊ฒฝ๋กœ ์ค‘ ์ตœ์†Œ ๋น„์šฉ์„ ๋จผ์ € ํƒ์ƒ‰ํ•˜๊ธฐ ์œ„ํ•จ @Override public int compareTo(Node n) { return this.weight - n.weight; } }
  • ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•˜๊ธฐ ์œ„ํ•ด ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•˜๋Š”๋ฐ, ๊ฐ€์ค‘์น˜๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ์œ„ํ•ด compareTo() ๋ฅผ ์˜ค๋ฒ„๋ผ์ด๋”ฉํ•œ๋‹ค.
private void dijkstra(int s, int e) { queue = new PriorityQueue<>(); dist[s][0] = 0; queue.add(new Node(s, 0, 0)); while(!queue.isEmpty()) { Node node = queue.poll(); int to = node.to; int weight = node.weight; int status = node.status; if (to == e) return; // ์ด๋™ํ•˜๋ ค๋Š” ๋…ธ๋“œ๊ฐ€ ํŠธ๋žฉ์ธ์ง€ ํ™•์ธํ•˜๊ณ , ํŠธ๋žฉ์ด๋ผ๋ฉด ์ด๋ฏธ ๋ฐŸ์€ ํŠธ๋žฉ์ธ์ง€ ํ™•์ธ // f = 0, ๋ฐŸ์ง€ ์•Š์€ ํŠธ๋žฉ์ด๊ฑฐ๋‚˜ ์ผ๋ฐ˜ ๋…ธ๋“œ / f = 1, ์ด๋ฏธ ๋ฐŸ์€ ํŠธ๋žฉ int f = 0; if (trapMap.containsKey(to)) { if ((status & trapMap.get(to)) != 0) f = 1; } forward(to, weight, status, f); backward(to, weight, status, f); } }
  • ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•˜์—ฌ ํŠธ๋žฉ ์—ฌ๋ถ€์— ๋”ฐ๋ผ f ๋ฅผ ์ง€์ •ํ•˜๊ณ , ์ •๋ฐฉํ–ฅ ํƒ์ƒ‰๊ณผ ์—ญ๋ฐฉํ–ฅ ํƒ์ƒ‰์„ ์ˆ˜ํ–‰ํ•œ๋‹ค.
private void forward(int to, int weight, int status, int f) { for (Node next : orgList[to]) { canForward = f; int nStatus = status; if (trapMap.containsKey(next.to)) { if ((status & trapMap.get(next.to)) != 0) canForward ^= 1; nStatus ^= trapMap.get(next.to); } if (canForward != 0) continue; if (dist[next.to][status] > weight + next.weight) { dist[next.to][status] = weight + next.weight; queue.add(new Node(next.to, dist[next.to][status], nStatus)); } } }
  • ์ •๋ฐฉํ–ฅ ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ,

    • ๋‹ค์Œ ๋ฐฉ๋ฌธํ•  ๋…ธ๋“œ์˜ ํŠธ๋žฉ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•˜๊ณ ,
    • ํŠธ๋žฉ์ธ ๊ฒฝ์šฐ, ํŠธ๋žฉ์˜ ๋ฐœ๋™ ์—ฌ๋ถ€๋ฅผ ํ™•์ธํ•œ๋‹ค.
    • canForward ๊ฐ€ 0 ์ธ ๊ฒฝ์šฐ(์ฆ‰, ํŠธ๋žฉ์ด์ง€๋งŒ ํ™œ์„ฑํ™” ๋˜์ง€ ์•Š์•˜๊ฑฐ๋‚˜ ์ผ๋ฐ˜ ๋…ธ๋“œ์ธ ๊ฒฝ์šฐ)๋งŒ queue ์— ํ•ด๋‹น ์ง€์ ์„ ์ถ”๊ฐ€ํ•œ๋‹ค.
    • 0์ธ ๊ฒฝ์šฐ: (f:canForward = 0:0 or 1:1)
  • ์—ญ๋ฐฉํ–ฅ์€ ๋ฐ˜๋Œ€

๐Ÿ“„ CODE

์ฝ”๋“œ ๋ณด๊ธฐ/์ ‘๊ธฐ๐Ÿ’ซ
import java.util.*; class Node implements Comparable<Node> { int to; int weight; int status; public Node(int to, int weight, int status) { this.to = to; this.weight = weight; this.status = status; } // ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ์œ„ํ•จ, ์—ฌ๋Ÿฌ ๊ฒฝ๋กœ ์ค‘ ์ตœ์†Œ ๋น„์šฉ์„ ๋จผ์ € ํƒ์ƒ‰ํ•˜๊ธฐ ์œ„ํ•จ @Override public int compareTo(Node n) { return this.weight - n.weight; } } class Maze { List<Node>[] orgList; List<Node>[] reverseList; Map<Integer, Integer> trapMap; Queue<Node> queue; int[][] dist; int canForward = 0; public Maze(int n, int[][] roads, int[] traps) { // List ์ดˆ๊ธฐํ™” orgList = new ArrayList[n + 1]; reverseList = new ArrayList[n + 1]; initList(n); fillList(roads); // ํŠธ๋žฉ ์ดˆ๊ธฐํ™”(์ขŒํ‘œ ์••์ถ•์„ ํ†ตํ•ด 2,5,10 -> 1,2,3์œผ๋กœ ์ €์žฅ) trapMap = new HashMap<>(); initTrap(traps); dist = new int[n+1][1<<trapMap.size()+1]; initDist(n); } private void initList(int n) { for (int i = 0; i < n + 1; i++) { orgList[i] = new ArrayList<>(); reverseList[i] =new ArrayList<>(); } } // ์ดˆ๊ธฐ ๊ฒฝ๋กœ์™€, ํŠธ๋žฉ์œผ๋กœ ์ธํ•ด ๋ฐ˜๋Œ€๋กœ ์ „ํ™˜๋˜๋Š” ๊ฒฝ๋กœ๋ฅผ ์ €์žฅ private void fillList(int[][] roads) { for (int[] road : roads) { int from = road[0]; int to = road[1]; int weight = road[2]; orgList[from].add(new Node(to, weight, 0)); reverseList[to].add(new Node(from, weight, 0)); } } // ์ขŒํ‘œ ์••์ถ• private void initTrap(int[] traps) { for (int i = 0; i < traps.length; i++) trapMap.put(traps[i], 1 << (i + 1)); } private void initDist(int n) { for (int i = 0; i < n + 1; i++) Arrays.fill(dist[i], Integer.MAX_VALUE); } public int solution(int start, int end) { dijkstra(start, end); int minCost = Integer.MAX_VALUE; for (int d : dist[end]) minCost = Math.min(minCost, d); return minCost; } private void dijkstra(int s, int e) { queue = new PriorityQueue<>(); dist[s][0] = 0; queue.add(new Node(s, 0, 0)); while(!queue.isEmpty()) { Node node = queue.poll(); int to = node.to; int weight = node.weight; int status = node.status; if (to == e) return; // ์ด๋™ํ•˜๋ ค๋Š” ๋…ธ๋“œ๊ฐ€ ํŠธ๋žฉ์ธ์ง€ ํ™•์ธํ•˜๊ณ , ํŠธ๋žฉ์ด๋ผ๋ฉด ์ด๋ฏธ ๋ฐŸ์€ ํŠธ๋žฉ์ธ์ง€ ํ™•์ธ // f = 0, ๋ฐŸ์ง€ ์•Š์€ ํŠธ๋žฉ์ด๊ฑฐ๋‚˜ ์ผ๋ฐ˜ ๋…ธ๋“œ / f = 1, ์ด๋ฏธ ๋ฐŸ์€ ํŠธ๋žฉ int f = 0; if (trapMap.containsKey(to)) { if ((status & trapMap.get(to)) != 0) f = 1; } forward(to, weight, status, f); backward(to, weight, status, f); } } // orgList = ์ •๋ฐฉํ–ฅ์— ๋Œ€ํ•œ ํƒ์ƒ‰ private void forward(int to, int weight, int status, int f) { for (Node next : orgList[to]) { canForward = f; int nStatus = status; if (trapMap.containsKey(next.to)) { if ((status & trapMap.get(next.to)) != 0) canForward ^= 1; nStatus ^= trapMap.get(next.to); } if (canForward != 0) continue; if (dist[next.to][status] > weight + next.weight) { dist[next.to][status] = weight + next.weight; queue.add(new Node(next.to, dist[next.to][status], nStatus)); } } } // reverseList = ์—ญ๋ฐฉํ–ฅ์— ๋Œ€ํ•œ ํƒ์ƒ‰ private void backward(int to, int weight, int status, int f) { for (Node next : reverseList[to]) { canForward = f; int nStatus = status; if (trapMap.containsKey(next.to)) { if ((status & trapMap.get(next.to)) != 0) canForward ^= 1; nStatus ^= trapMap.get(next.to); } if (canForward != 1) continue; if (dist[next.to][status] > weight + next.weight) { dist[next.to][status] = weight + next.weight; queue.add(new Node(next.to, dist[next.to][status], nStatus)); } } } } class Solution { public int solution(int n, int start, int end, int[][] roads, int[] traps) { Maze m = new Maze(n, roads, traps); return m.solution(start, end); } }

โœ๏ธ Review

  • ์‹œ์ž‘์ง€์ ๋ถ€ํ„ฐ ์ข…๋ฃŒ์ง€์ ๊นŒ์ง€์˜ ํƒ์ƒ‰์„ ์œ„ํ•œ ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜๊ณผ, ํŠธ๋žฉ์„ ๋ฐฉ๋ฌธํ•œ ๊ฒฝ์šฐ ์—ฐ๊ฒฐ๋œ ๊ธธ์„ Switching ํ•ด์ฃผ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ํ•„์š”ํ–ˆ๋‹ค.
  • ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰์€ DFS๋‚˜ BFS๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ์—ฐ๊ฒฐ๋œ ๊ธธ์— ๋Œ€ํ•œ Switching ์€ ์–ด๋–ป๊ฒŒ ํ•ด์•ผํ•  ์ง€ ๊ฐ์ด ์˜ค์ง€ ์•Š์•˜๋‹ค. ๊ธธ์˜ ๋น„์šฉ์€ ๊ณ ์ •์ ์ด์ง€๋งŒ, ๋ฐฉํ–ฅ๋งŒ ๋ฐ”๊ฟ”์ค˜์•ผ ํ–ˆ๋‹ค.
  • ์ฐธ๊ณ  ๋ธ”๋กœ๊ทธ๋ฅผ ๋ณด๋ฉด์„œ ์ดํ•ดํ•˜๋Š”๋ฐ, "๊ธฐ๋ณธ์ ์ธ ๋กœ์ง์€ ์ตœ๋‹จ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋Š” ๊ฒƒ์ด๋‹ค. ๋˜ํ•œ ์กฐ๊ฑด์ƒ ๋‘ ์ง€์  ๊ฐ„ ์—ฌ๋Ÿฌ ๊ธธ์ด ์กด์žฌํ•  ์ˆ˜ ์žˆ๊ณ , ๊ธธ๋งˆ๋‹ค์˜ ๊ฐ€์ค‘์น˜๊ฐ€ ์žˆ๊ธฐ์—, ๊ทธ๋ž˜์„œ ๋˜‘๊ฐ™์€ ๊ฒฝ๋กœ๋ผ ํ•˜๋”๋ผ๋„ ์ž‘์€ ๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ€์ง„ ๊ฐ„์„ ์„ ์œ„์ฃผ๋กœ ํƒ์ƒ‰์„ ํ•ด์•ผํ•˜๋ฏ€๋กœ ์šฐ์„ ์ˆœ์œ„ ํ๋ฅผ ์‚ฌ์šฉํ•œ ๋‹ค์ต์ŠคํŠธ๋ผ๊ฐ€ ๋ฌธ์ œ์˜ ๋ณธ์งˆ์ž„์„ ์•Œ์•„๋‚ผ ์ˆ˜ ์žˆ๋‹ค." ์ด๋Ÿฌํ•œ ์ƒ๊ฐ์„ ํ•  ์ˆ˜ ์žˆ๋„๋ก ๋…ธ๋ ฅํ•ด์•ผ ๊ฒ ๋‹ค.
  • ๋น„ํŠธ๋งˆ์Šคํ‚น์„ ์‚ฌ์šฉํ•œ ํ’€์ด๋ฅผ ์ฐธ๊ณ ํ–ˆ๋Š”๋ฐ, ์ฝ”๋“œ๋ฅผ ๋ณด๊ณ  ๋ด๋„ ์ดํ•ด๊ฐ€ ์–ด๋ ค์šด ๊ฒƒ ๊ฐ™๋‹ค. ์ž์ฃผ ์‚ฌ์šฉํ•ด๋ณด์ง€ ์•Š์€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด์ด์„œ ๊ทธ๋Ÿฐ ๊ฒƒ ๊ฐ™๋‹ค. ๋น„ํŠธ๋งˆ์Šคํ‚น์„ ์‚ฌ์šฉํ•˜๋Š” ๊ธฐ๋ณธ ์˜ˆ์ œ๋ฅผ ํ’€์–ด๋ด์•ผ๊ฒ ๋‹ค.

๐Ÿ“• ์ฐธ๊ณ 

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] 2021 ์นด์นด์˜ค ์ธํ„ด #4 ๋ฏธ๋กœ ํƒˆ์ถœ (Java)

@Seongukbaek
๋ฐฐ์šฐ๊ณ  ์ •๋ฆฌํ•˜๊ณ  ๊ณต์œ ํ•˜๋Š” ๋Œ€ํ•™์ƒ ๋ฐฑ์„ฑ์šฑ์ž…๋‹ˆ๋‹ค ๐Ÿ˜€